BOJ_1707_이분 그래프

이분 그래프(Bipartite Graph)인지 확인하는 문제

이분 그래프가 되기 위해서는 인접한 노드의 색이 달라야 하기 때문에 그래프를 입력 받고 인접한 노드를 탐색한다

체크해야 할 것 :

1. 이전에 탐색한 노드와 현재 노드의 색이 다른지 -> 방문 배열을 int로 줘서 확인함
2. 모든 노드를 돌고 있는지

모든 노드가 이어져있는 연결 그래프가 아닐 수 있다는 점을 간과해서 첫 시도에 성공하지 못했다

반복문으로 모든 노드를 돌면서 방문처리 하면 된다
Queue의 구현체로는 LinkedList보다 메모리 효율적인 ArrayDeque를 사용하였다

LinkedList 와 ArrayDeque를 바꿔서 해봤는데 별로 유의미한 차이는 없다

package BJO;  
  
import java.util.ArrayDeque;  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Queue;  
import java.util.Scanner;  
  
public class BJO_1707_이분그래프 {  
  
    public static void main(String[] args) {  
       Scanner scan = new Scanner(System.in);  
       // 테스트의 개수  
       int K = scan.nextInt();  
       Loop:  
       for (int i = 0; i < K; i++) {  
          // 정점의 개수  
          int V = scan.nextInt();  
          // 간선의 개수  
          int E = scan.nextInt();  

		// 정점에 연결된 다른 정점을 저장할 리스트
          List<Integer>[] list = new ArrayList[V + 1];  

		// 배열 초기화
          for (int j = 1; j <= V; j++) {  
             list[j] = new ArrayList<>();  
          }  
  
          for (int j = 0; j < E; j++) {  
             int num = scan.nextInt();  
             int link = scan.nextInt();  
  
             list[num].add(link);  
             list[link].add(num);  
          }  

		// 0은 방문하지 않은 노드. 1 또는 2로 색칠을 하며 간다
          int[] visited = new int[V + 1];  
          Queue<Integer> que = new ArrayDeque<>();  
  
          for (int j = 1; j <= V; j++) {  
             if (visited[j] == 0) {  
                que.offer(j);  
                boolean res = bfs(que, list, visited);  
  
                if (!res) {  
                   System.out.println("NO");  
                   continue Loop;  
                }  
             }  
          }  
  
          System.out.println("YES");  
       }  
    }  
  
    static boolean bfs(Queue<Integer> que, List<Integer>[] list, int[] visited) {  
       while (!que.isEmpty()) {  
          int n = que.poll();  
  
          for (int j = 0; j < list[n].size(); j++) {  
             int node = list[n].get(j);  
             if (visited[node] == 0) {  
                visited[node] = visited[n] == 1 ? 2 : 1;  
                que.offer(node);  
             }  
  
             if (visited[node] == visited[n]) {  
                return false;  
             }  
          }  
       }  
  
       return true;  
    }  
}

#이분그래프